// Copyright (C) 2011  Andrew H. Chan
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
// 
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

#ifndef _BUNEMAN_H__
#define _BUNEMAN_H__

#include "typedefs.h"
#include "input_data.h"
#include "graph.h"
#include "graphdata.h"

class Buneman {
    public:
        typedef Graph<cvector, Segment_edge_data, Segment_graph_data<cvector> > Segment_graph;
        typedef Graph<cvector, Level1_edge_data, Level1_data<cvector> > Level1_graph;
        typedef Graph<dcvector, Level2_edge_data, Level2_data<dcvector> > Level2_graph;

        Buneman(Input_data const& in_data);

        // execute sequence of functions to analyze data
        int execute();

        // prune rows and columns
        int preprocess_data(Input_data const& in_data);

        // compute buneman property for each segment
        int compute_buneman_property();

        // create buneman graph for each segment
        int create_segment_graphs();

        // helper to create buneman graph for each segment
        int buneman_neighbor(uint seg_id, boost::unordered_set<cvector>& v_set, cvector const& vertex, Segment_graph& cur_graph);

        // creates and solves ILP for each segment
        int solve_segment_ILPs();

        // compute buneman property for data as a whole
        int compute_all_buneman_property();

        // construct_level1_graph
        int construct_level1_graph();

        // adds vertices to level 1 buneman graph
        int add_level1_vertices(Level1_graph& level1_graph, int segment, cvector const& part_vertex);

        int add_level1_edges(Level1_graph& level1_graph);

        // create level 2 graph
        int construct_level2_graph();

        // adds vertices to level 2 buneman graph
        int add_level2_vertices(Level2_graph& level2_graph, int segment, dcvector const& part_vertex, int heuristics);
        
        int add_level2_edges(Level2_graph& level2_graph);

        //int get_subset(bvector& mask);

        // depth first search to check connectivity of graph 
        template<typename VertexT, typename EdgeT, typename GraphDataT>
        int dfs_search(Graph<VertexT, EdgeT, GraphDataT> const& graph, VertexT const& vert, boost::unordered_set<VertexT>& v_set, int& num_vert_reached);

        //template<class VertexT> int create_reassort_ILP(Graph<VertexT>& graph);
        // data members

        // keep copy of original data passed in
        Input_data in_data; 

        // processed data
        std::vector<std::vector<cvector> > row_data;

        // bit vector indicating which columns were pruned
        std::vector<bool> all_remove_col;

        // total number of sites after column pruning
        uint tot_new_num_sites;
        // map sites in row_data to original data
        std::vector<int> map_to_data; 
        // site where each segment starts
        std::vector<int> segment_start;
        // site where each segment ends plus 1
        std::vector<int> segment_end;
        // which segment each site belongs to
        std::vector<int> site_belong;

        // buneman property for pairs of sites for each segment
        std::vector<std::vector<char> > bprop;

        // buneman graphs for each segment
        std::vector<Segment_graph > buneman_graphs;

        // buneman property for pairs of sites for whole data
        std::vector<char> allbprop;
        // size of projection for each pair of sites
        std::vector<int> allbprop_count;

        // level 1 buneman graph 
        Level1_graph level1_graph;
        
        // level 2 buneman graph
        Level2_graph level2_graph;

        // Steiner vertices for each segment
        std::vector<std::vector<cvector> > steiner_vertices;

        // debug
        uint num_edges;
        int vertices_not_kept;
        int vertices_not_kept2;
        int num_reassort_nonunique;
        int num_vertices_added;
        uint num_reassort_edges;
};
#endif
